1704C - Virus - CodeForces Solution

def solve():
    n, m = readIntArr()
    a = readIntArr()
    a.sort()
            gaps = []
    for i in range(m):
        x, y = a[i % m], a[(i + 1) % m]
        if x >= y:
            x -= n
        if y - x - 1 > 0:
            gaps.append(y - x - 1)
    gaps.sort(reverse=True)
        
    savedtotal = 0
    subtract = 0
    for x in gaps:
        saved = x - 2 * subtract
                if saved <= 0:
            continue
        if saved <= 2:
            savedtotal += 1
            subtract += 1          else:
            savedtotal += saved - 1
            subtract += 2
    ans = n - savedtotal
    return ans

def main():
    
    t = int(input())
    allans = []
    for _ in range(t):
        allans.append(solve())
    multiLineArrayPrint(allans)
    
    return

import sys
input=sys.stdin.buffer.readline  
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr):     dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
 
inf=float('inf')
 
from math import gcd,floor,ceil
import math
 
for _abc in range(1):
    main()